package algorithm.middle;

import java.util.Queue;
import java.util.Stack;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: IsValidSerialization331
 * @description: 331. 验证二叉树的前序序列化
 * @date 2021/3/1515:14
 * @since V1.0
 * 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
 *
 *      _9_
 *     /   \
 *    3     2
 *   / \   / \
 *  4   1  #  6
 * / \ / \   / \
 * # # # #   # #
 *
 * 例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
 *
 * 给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
 *
 * 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
 *
 * 你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
 *
 * 输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
 * 输出: true
 *
 * 示例 2:
 *
 * 输入: "1,#"
 * 输出: false
 *
 * 示例 3:
 *
 * 输入: "9,#,#,1"
 * 输出: false
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class IsValidSerialization331 {

    public static void main(String[] args) {
        isValidSerialization("1,#,#,#");

    }

    //依次入栈。两个##加上根节点合成一个#
    public static boolean isValidSerialization(String preorder) {
        String[] split = preorder.split(",");
        Stack<String> stack = new Stack<>();
        for (int i=0;i<split.length;i++){
            if ("#".equals(split[i]) && !stack.isEmpty() && "#".equals(stack.peek())){
                //4##可以消除为#
                stack.pop();
                if (!stack.isEmpty()){
                    stack.pop();
                }else {
                    return false;
                }
                i--;
            }else {
                stack.push(split[i]);
            }
        }
        if (stack.size()==1 && stack.pop().equals("#")){
            return true;
        }
        return false;
    }

    /**
     *
     *     入度：有多少个节点指向它；
     *     出度：它指向多少个节点。
     *     我们知道在树（甚至图）中，所有节点的入度之和等于出度之和。可以根据这个特点判断输入序列是否为有效的！
     *     数字：入度1，出度2
     *     #：入度1，出度0
     */
    public static boolean fun(String preorder) {
        String[] split = preorder.split(",");
        //diff = 出度 - 入度 。 根节点没有入度，一开始-1则为负数了，所以一开始默认给根节点一个入度1。
        int diff = 1;
        for(String x:split){
            diff = diff - 1;
            if (diff<0){
                return false;
            }
            if (!x.equals("#")){
                diff = diff + 2;
            }
        }
        return diff == 0;
    }


}
